#define _CRT_SECURE_NO_WARNINGS 1
#include <string.h>
#include<stdlib.h>
#include <math.h>
#include<stdio.h>
//struct student
//{
//	int x ;
//	int c ;
//};
//int main()
//{
//	int n=0,a = 0;
//	scanf("%d %d", &n, &a);
//	struct student stu[100],stt;
//	int i = 0;
//	for (i = 0; i < n; i++)
//	{
//		scanf("%d %d", &stu[i].x,&stu[i].c);
//	}
//	int j = 0;
//	for (i = 0; i < n; i++)
//	{
//		for (j = 0; j < n - i-1; j++)
//		{
//			if (stu[j].c <=stu[j + 1].c)
//			{
//				stt = stu[j];
//				stu[j] = stu[j + 1];
//				stu[j + 1] = stt;
//			}
//		}
//	}
//	int d = a * 1.5;
//	int s = 0;
//	for (i = 0; i < n; i++)
//	{
//		if (stu[i].c >= stu[d].c)
//		{
//			s++;
//		}
//	}
//	printf("%d %d\n", stu[d].c , s);
//	for (i = 0; i < s; i++)
//	{
//		printf("%d %d\n", stu[i].x, stu[i].c);
//	}
//	return 0;
//}


//int main()
//{
//	int a = 0;
//	int n = 0;
//	scanf("%d", &n);
//	int i = 0;
//	int  num[1000] = {0};
//	int num2[1000] = { 0 };
//	for (i = 2; i < n; i++)
//	{
//		if (n%i == 0)
//		{
//			num[a] = i;
//			a++;
//		}
//	}
//	int k = 0,l=0,p=0;
//	for (i = 0; i < a; i++)
//	{
//		if (num[i] == 2)
//		{
//			num2[0] = 2;
//			l++;
//			continue;
//		}
//		for (int j = 2; j < num[i]; j++)
//		{
//			if (num[i] % j == 0)
//			{
//				p++;
//			}
//		}
//		if (p == 0)
//		{
//			num2[l] = num[i];
//			l++;
//		}
//		p = 0;
//	}
//	int x = 0;
//	for (i = 0; i < l; i++)
//	{
//		x = num2[i];
//		for (int j = i+1; j < l; j++)
//		{
//			if (x*num2[j]==n)
//			{
//				printf("%d", num[j]);
//				return 0;
//			}
//		}
//	}
//	return 0;
//}


//int main()
//{
//	int a = 0;
//	scanf("%d", &a);
//	int i = 0;
//	int num[100000] = { 0 };
//	for (i = 0; i < a; i++)
//	{
//		scanf("%d",&num[i]);
//	}
//	long long d = 0,t=0;
//	for (i = 0; i < a; i++)
//	{
//		for (int j = 0; j < a - i-1; j++)
//		{
//			if (num[j] > num[j + 1])
//			{
//				d++;
//			}
//		}
//	}
//	printf("%lld",d);
//	return 0;
//}

//#include<stdio.h>
//int main(void)
//{
//	int n, a[100000], i=0, j=0, temp=0, count=0;
//	scanf("%d", &n);
//		for (i = 0; i < n; i++)
//			scanf("%d", &a[i]);
//		for (i = 0; i < n; i++)
//			for (j = 0; j < n - i-1; j++)
//				if (a[j] > a[j + 1])
//				{
//					count++;
//				}
//	printf("%d\n", count);
//	return 0;
//}



//#include <iostream>
//using namespace std;
//const int n = 1e6 + 10;
//int num[100];
//int n = 0;
//void quick(int num[100], int l, int r)
//{
//	if (l >= r) return;
//	int x = num[l], i = l - 1, j = r + 1;
//	do { i++; } while (num[i] < num[l]);
//	do { j--; } while (num[j] > num[l]);
//	quick(num, l, j);
//	quick(num, j + 1, r);
//}
//int main()
//{
//	scanf("%d", &n);
//	int i = 0;
//	for (i = 0; i < n; i++)
//	{
//		scanf("%d", &num[i]);
//	}
//	int l = 0;
//	int r = n - 1;
//	quick (num, r, l);
//	return 0;
//}
